package com.shuang.tree16;


import java.util.LinkedList;
import java.util.Queue;

public class Connect {

    //单层遍历的时候先记录一下本层的头部节点，然后在遍历后面的 让前一个节点指向本节点
    public Node connect(Node root) {

        Queue<Node> tmpQueue = new LinkedList<Node>();

        if (root != null)
            tmpQueue.add(root);

        while (tmpQueue.size() != 0) {

            int size = tmpQueue.size();

            //当前层的头节点（最左边的）
            Node cur = tmpQueue.poll();

            if (cur.left != null)
                tmpQueue.add(cur.left);

            if (cur.right != null)
                tmpQueue.add(cur.right);

            //遍历后面的节点
            for (int index = 1; index < size; index++) {
                //拿到下一个节点
                Node next = tmpQueue.poll();

                if (next.left != null)
                    tmpQueue.add(next.left);

                if (next.right != null)
                    tmpQueue.add(next.right);

                //连接上 下一个节点
                cur.next = next;

                //走到下一个节点位置
                cur = next;
            }
        }

        return root;
    }
}
